﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._20
{
    public class Leetcode19
    {
        public void Test()
        {
            try
            {
                ListNode head = new ListNode(1);
              
                head.next = new ListNode(2);

                head.next.next = new ListNode(3);

                //head.next.next.next = new ListNode(4);
                //head.next.next.next.next = new ListNode(5);
                var test = RemoveNthFromEnd(head, 3);

            }
            catch (Exception ex)
            { }
        }

        /*
         19. Remove Nth Node From End of List 

        Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass. 
         */

        public ListNode RemoveNthFromEnd(ListNode head, int n)
        {
            if (head.next == null)
                return null;
            ListNode tempNode = head;
            int totalCount = 1;
            while (tempNode.next != null)
            {
                tempNode = tempNode.next;
                totalCount++;
            }

            tempNode = head;
            int loopCount = totalCount - n;
            if (loopCount == 0)
                return head.next;
            return RemoveNode(head, loopCount, 0);
        }

        private ListNode RemoveNode(ListNode head, int n, int index)
        {
            if (n == index + 1)
            {
                head.next = head.next.next;
                return head;
            }
            head.next = RemoveNode(head.next, n, ++index);
            return head;
        }
    }


    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int x) { val = x; }
    }

}
